package com.heima.leetcode.practice;

import java.util.Arrays;
import java.util.Comparator;

/**
 * leetcode 322. 零钱兑换一
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/11 10:47
 */
public class E322 {
    /*
            0    1    2    3    4    5    amount
        1   0    1    11   111  1111 11111
        2   0    1    2    21   22   221
        5   0    1    2    21   22   5
      面值

      其中dp[i][j]表示使用前i种硬币，凑成金额j所需要的最少硬币的数量

      if(总金额小于当前面额){
          dp[i][j] = dp[i-1][j]
      }else{
          dp[i][j] = Math.min(dp[i-1][j], 1 + dp[i][amount-currCoin])
      }
     */

    /**
     * <h3>方法一：动态规划，用二维数组</h3>
     * @param coins 硬币面额数组
     * @param amount 目标金额
     * @return 最少硬币数量，若无解，返回-1
     */
    public int coinChange1(int[] coins, int amount) {
        // 1. 构建dp数组
        int rows = coins.length;
        int columns = amount + 1;
        int[][] dp = new int[rows][columns];
        // 2. 对dp数组的第一行进行初始化
        for (int j = 1; j < columns; j++) { // 这里至于为什么总面值0的时候不初始为amount+1，是因为题目要求这种情况返回0
            if (coins[0] <= j){
                dp[0][j] = 1 + dp[0][j - coins[0]]; // 装得下则1 + 剩余的待凑金额的最少硬币数量
            }else {
                // 无法凑成目标金额，返回最大值，这里选用amount+1是因为最小面值肯定是1，
                // amount+1个最小的面值都肯定超过目标金额了
                // 这里不选用Integer.MAX_VALUE是因为还会参与加法运算（上述if条件内的情况），会溢出
                dp[0][j] = amount + 1;
            }
        }
        // 3. 逐行遍历dp数组，计算dp[i][j]
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (j < coins[i]){
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = Math.min(dp[i - 1][j], 1 + dp[i][j - coins[i]]);
                }
            }
        }
        // 4. 返回dp数组右下角
        return dp[rows - 1][columns - 1] >= amount + 1 ? -1 : dp[rows - 1][columns - 1];
    }

    /**
     * <h3>方法二：动态规划，用一维数组</h3>
     * @param coins 硬币面额数组
     * @param amount 目标金额
     * @return 最少硬币数量，若无解，返回-1
     */
    public int coinChange2(int[] coins, int amount) {
        // 1. 构建dp数组
        int[] dp = new int[amount + 1];
        // 2. 对dp数组的第一行进行初始化
        for (int j = 1; j < dp.length; j++) { // 这里至于为什么总面值0的时候不初始为amount+1，是因为题目要求这种情况返回0
            if (coins[0] <= j){
                dp[j] = 1 + dp[j - coins[0]]; // 装得下则1 + 剩余的待凑金额的最少硬币数量
            }else {
                // 无法凑成目标金额，返回最大值，这里选用amount+1是因为最小面值肯定是1，
                // amount+1个最小的面值都肯定超过目标金额了
                // 这里不选用Integer.MAX_VALUE是因为还会参与加法运算（上述if条件内的情况），会溢出
                dp[j] = amount + 1;
            }
        }
        // 3. 逐行遍历dp数组，计算dp[i][j]
        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j < dp.length; j++) {
                if (j >= coins[i]){
                    dp[j] = Math.min(dp[j], 1 + dp[j - coins[i]]); // j - coins[i]的金额肯定比j小，在j前面，在数组中在j前面，因为使用前0-i中面额凑，这里要用正序遍历
                }
            }
        }
        // 4. 返回dp数组右下角
        return dp[dp.length - 1] >= amount + 1 ? -1 : dp[dp.length - 1];
    }
}
